class Solution
{
public:
    void quick_sort(vector<int> &arr, int left, int right, int pos)
    {
        int random = left + rand() % (right - left + 1);
        swap(arr[left], arr[random]);
        int lend = left + 1, rhead = right;
        for (int i = left + 1; i <= rhead; ++i)
        {
            while (i <= rhead && arr[i] > arr[left])
                swap(arr[i], arr[rhead--]);
            if (arr[i] < arr[left])
                swap(arr[i], arr[lend++]);
        }
        swap(arr[left], arr[lend - 1]);
        if (rhead >= pos && lend - 1 <= pos)
            return;
        // 如果右边比较小，那我右边还需要继续排序
        else if (rhead < pos)
            quick_sort(arr, rhead + 1, right, pos);
        else
            quick_sort(arr, left, lend - 1, pos);
    }
    // 转换为找第k个大的数
    vector<int> getLeastNumbers(vector<int> &arr, int k)
    {
        if (k == 0)
            return {};
        srand(time(NULL));
        quick_sort(arr, 0, arr.size() - 1, k - 1);
        vector<int> ans;
        for (int i = 0; i < k; ++i)
            ans.push_back(arr[i]);
        return ans;
    }
};